package HashTable;

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;

/*      给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
        注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

        示例 1:
        输入: s = "anagram", t = "nagaram"
        输出: true

        示例 2:
        输入: s = "rat", t = "car"
        输出: false*/
public class lc242 {
    public static void main(String[] args) {
        String s= "anagram";
        String t="nagaram";
        System.out.println(isAnagram1(s, t));
        System.out.println(isAnagram1(s, t));
    }
    public static boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        char[] sstr=s.toCharArray();
        char[] tstr=t.toCharArray();
        Arrays.sort(sstr);
        Arrays.sort(tstr);
        for (int i = 0; i <s.length() ; i++) {
            if(sstr[i]!=tstr[i]) return false;
        }
        return true;
    }

    public static boolean isAnagram1(String s, String t) {  //先排序
        if(s.length()!=t.length()) return false;
        char[] sstr=s.toCharArray();
        char[] tstr=t.toCharArray();
        for (int i = 0; i < sstr.length ; i++) {
            for (int j = 0; j < sstr.length-i-1 ; j++) {
                if (sstr[j]>sstr[j+1]) {
                    char temp=sstr[j];
                    sstr[j]=sstr[j+1];
                    sstr[j+1]=temp;
                }
            }
        }
        for (int i = 0; i < sstr.length ; i++) {
            for (int j = 0; j < sstr.length-i-1 ; j++) {
                if (tstr[j]>tstr[j+1]) {
                    char temp=tstr[j];
                    tstr[j]=tstr[j+1];
                    tstr[j+1]=temp;
                }
            }
        }
        for (int i = 0; i < sstr.length ; i++) {
            if(sstr[i]!=tstr[i]) return false;
        }
        return true;
    }

    public static boolean isAnagram_hashmap(String s, String t) { //建立真正的哈希表
        if(s.length()!=t.length()) return false;
        char[] sstr=s.toCharArray();
        char[] tstr=t.toCharArray();
        HashMap<Character,Integer> map=new HashMap<>();//记录字母及其出现次数
        //把sstr中的各个字母及其出现次数记录在map中
        for (char c: sstr
             ) {
        if(!map.containsKey(c)){  //若不存在，则将其放入map
            map.put(c,1);
        }else{  //若存在，则将其value+1，更新value值
            int count=map.get(c);
            count++;
            map.put(c,count);
        }
        }

        //将tstr中的元素依次提出，若map的key中有该元素，将其对应的value-1
        for (char c:tstr
             ) {
            if(!map.containsKey(c)){  //若不存在，则将其放入map
                map.put(c,-1);
            }else{  //若存在，则将其value-1，更新value值
                int count=map.get(c);
                count--;
                map.put(c,count);
            }
        }

        //遍历value的值，看是否都为0
        for (int val:map.values()
             ) {
            if(val!=0) return false;
        }
        return true;

    }
    public static boolean isAnagram_arr(String s, String t) { //把一个数组当作hash表
        if(s.length()!=t.length()) return false;
        char[] sstr=s.toCharArray();
        char[] tstr=t.toCharArray();
        int[] count=new int[26];//记录字母出现的次数
        for (char c:sstr
             ) {
            count[c-'a']++;
        }
        for (char c:tstr
        ) {
            count[c-'a']--;
        }
        for (int val:count
             ) {
            if(val!=0) return false;
        }
        return true;

    }
}
